<html>
<head><meta charset="utf-8"><title>type inference algorithm · t-compiler/help · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/index.html">t-compiler/help</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html">type inference algorithm</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="220010569"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220010569" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> kev <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220010569">(Dec 15 2020 at 17:10)</a>:</h4>
<p>Hi, </p>
<p>Anyone knows why the type checker gives a type error for k?</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">fn</span> <span class="nf">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">v</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">vec</span><span class="o">!</span><span class="p">[</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">,</span><span class="mi">3</span><span class="p">,</span><span class="mi">4</span><span class="p">];</span><span class="w"></span>

<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">v</span><span class="p">.</span><span class="n">iter</span><span class="p">().</span><span class="n">collect</span><span class="p">();</span><span class="w"></span>
<span class="w">    </span><span class="n">k</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="mi">4</span><span class="p">);</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>



<a name="220010874"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220010874" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220010874">(Dec 15 2020 at 17:12)</a>:</h4>
<p>What should the type of <code>k</code> be? <code>Vec&lt;i32&gt;</code> or some other type with a <code>push</code> method?</p>



<a name="220010925"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220010925" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mario Carneiro <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220010925">(Dec 15 2020 at 17:13)</a>:</h4>
<p>Actually <code>Vec&lt;&amp;i32&gt;</code> in this case</p>



<a name="220010960"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220010960" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> kev <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220010960">(Dec 15 2020 at 17:13)</a>:</h4>
<p><span class="user-mention silent" data-user-id="133247">bjorn3</span> <a href="#narrow/stream/182449-t-compiler.2Fhelp/topic/type.20inference.20algorithm/near/220010874">said</a>:</p>
<blockquote>
<p>What should the type of <code>k</code> be? <code>Vec&lt;i32&gt;</code> or some other type with a <code>push</code> method?</p>
</blockquote>
<p>What other type can it be?</p>



<a name="220010985"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220010985" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mario Carneiro <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220010985">(Dec 15 2020 at 17:13)</a>:</h4>
<p>anything implementing <code>FromIterator&lt;Item=&amp;i32&gt;</code></p>



<a name="220011064"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220011064" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mario Carneiro <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220011064">(Dec 15 2020 at 17:14)</a>:</h4>
<p>like a <code>HashSet</code> I guess</p>



<a name="220011092"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220011092" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220011092">(Dec 15 2020 at 17:14)</a>:</h4>
<p>well that doens't have a <code>push</code> method</p>



<a name="220011119"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220011119" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220011119">(Dec 15 2020 at 17:14)</a>:</h4>
<p><code>BinaryHeap</code> does have a <code>push</code> method.</p>



<a name="220011149"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220011149" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220011149">(Dec 15 2020 at 17:14)</a>:</h4>
<p><a href="https://doc.rust-lang.org/stable/std/collections/struct.BinaryHeap.html#method.push">https://doc.rust-lang.org/stable/std/collections/struct.BinaryHeap.html#method.push</a></p>



<a name="220011152"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220011152" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220011152">(Dec 15 2020 at 17:14)</a>:</h4>
<p>But this is an intentional limitation – calls to inherent methods stop the type checker in its tracks if the receiver hasn't been inferred yet</p>



<a name="220011261"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220011261" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> kev <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220011261">(Dec 15 2020 at 17:15)</a>:</h4>
<p><span class="user-mention silent" data-user-id="211727">Jonas Schievink</span> <a href="#narrow/stream/182449-t-compiler.2Fhelp/topic/type.20inference.20algorithm/near/220011152">said</a>:</p>
<blockquote>
<p>But this is an intentional limitation – calls to inherent methods stop the type checker in its tracks if the receiver hasn't been inferred yet</p>
</blockquote>
<p>So even if there were enough implicit constraints to determine the actual type, ie methods that are only on vec, it would still err? without the explicit type annotation</p>



<a name="220011390"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220011390" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220011390">(Dec 15 2020 at 17:16)</a>:</h4>
<p>Only if there was exactly one applicable <code>FromIterator</code> impl would it be allowed I think.</p>



<a name="220011472"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220011472" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220011472">(Dec 15 2020 at 17:17)</a>:</h4>
<p>Yeah, inherent methods do not drive inference at all, only trait methods</p>



<a name="220011684"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220011684" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> kev <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220011684">(Dec 15 2020 at 17:18)</a>:</h4>
<p>Oh got it, thank you</p>



<a name="220012056"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220012056" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220012056">(Dec 15 2020 at 17:21)</a>:</h4>
<p><span class="user-mention" data-user-id="211727">@Jonas Schievink</span> I don't think trait methods drive inference that way either? <a href="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=c7ed95825a7b79af8c2517f8f9556279">e.g.</a></p>



<a name="220012696"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220012696" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220012696">(Dec 15 2020 at 17:25)</a>:</h4>
<p>hmm, yeah</p>



<a name="220012814"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220012814" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220012814">(Dec 15 2020 at 17:26)</a>:</h4>
<p>The rules here are complicated, it seems. Having only a single impl for a trait <em>can</em> drive inference forwards in some situations.</p>



<a name="220013283"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220013283" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> kev <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220013283">(Dec 15 2020 at 17:29)</a>:</h4>
<p>The following also fails (just added a bar function to code posted by Florian):</p>
<div class="codehilite"><pre><span></span><code>trait Foo {
    fn foo(&amp;self) {}
}

struct S;
impl Default for S {
    fn default() -&gt; Self { S }
}

impl Foo for S { }

fn main() {
    let s = Default::default();
    s.foo();
    bar(&amp;s);
}

fn bar(_s : &amp;S) {}
</code></pre></div>



<a name="220013363"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220013363" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> kev <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220013363">(Dec 15 2020 at 17:30)</a>:</h4>
<p>But if bar is placed before s.foo() it passes</p>



<a name="220013414"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220013414" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> kev <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220013414">(Dec 15 2020 at 17:30)</a>:</h4>
<p>I would have thought that it would have globally inferred the type from it's usage in bar, regardless of the order</p>



<a name="220013644"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220013644" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220013644">(Dec 15 2020 at 17:32)</a>:</h4>
<p><span class="user-mention silent" data-user-id="211727">Jonas Schievink</span> <a href="#narrow/stream/182449-t-compiler.2Fhelp/topic/type.20inference.20algorithm/near/220011152">said</a>:</p>
<blockquote>
<p>But this is an intentional limitation – calls to inherent methods stop the type checker in its tracks if the receiver hasn't been inferred yet</p>
</blockquote>
<p>That's what I was trying to say with this ^</p>



<a name="220013688"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220013688" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220013688">(Dec 15 2020 at 17:32)</a>:</h4>
<p>Rust type checking is not (fully) constraint-based, so ordering matters</p>



<a name="220013763"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220013763" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> kev <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220013763">(Dec 15 2020 at 17:33)</a>:</h4>
<p><span class="user-mention silent" data-user-id="211727">Jonas Schievink</span> <a href="#narrow/stream/182449-t-compiler.2Fhelp/topic/type.20inference.20algorithm/near/220013644">said</a>:</p>
<blockquote>
<p><span class="user-mention silent" data-user-id="211727">Jonas Schievink</span> <a href="#narrow/stream/182449-t-compiler.2Fhelp/topic/type.20inference.20algorithm/near/220011152">said</a>:</p>
<blockquote>
<p>But this is an intentional limitation – calls to inherent methods stop the type checker in its tracks if the receiver hasn't been inferred yet</p>
</blockquote>
<p>That's what I was trying to say with this ^</p>
</blockquote>
<p>Is it intentional for readability?</p>



<a name="220014401"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220014401" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220014401">(Dec 15 2020 at 17:37)</a>:</h4>
<p>no</p>



<a name="220015172"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220015172" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> kev <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220015172">(Dec 15 2020 at 17:43)</a>:</h4>
<p>Hmm that's the only reason I can think of, so when reading code, the reader can more or less know what the type of <code>s</code> is in s.foo(). Instead of needing to read past the method call</p>



<a name="220018248"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220018248" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mario Carneiro <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220018248">(Dec 15 2020 at 18:05)</a>:</h4>
<p>well inference gets a lot more complicated if you don't do something like this, since you get cycles. Even if it can be done, I think you could make some <em>very</em> surprising non-local behaviors where different types get chosen in one function depending on whether another unrelated and unused function exists or not</p>



<a name="220018345"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/182449-t-compiler/help/topic/type%20inference%20algorithm/near/220018345" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mario Carneiro <a href="https://rust-lang.github.io/zulip_archive/stream/182449-t-compiler/help/topic/type.20inference.20algorithm.html#220018345">(Dec 15 2020 at 18:05)</a>:</h4>
<p>It starts to smell like C++ operator overloading</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>